package org.example.algorithm.array;

//41. 缺失的第一个正数
//输入：nums = [1,2,0]
//输出：3
//解释：范围 [1,2] 中的数字都在数组中。
public class FirstMissingPositiveSolution {
    public static void main(String[] args) {
        int[] nums = {1,1};
        FirstMissingPositiveSolution solution = new FirstMissingPositiveSolution();
        int ans = solution.firstMissingPositive(nums);
        System.out.println(ans);
    }

    //交换法
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        int cur = 0;
        while (cur < len) {
            if (nums[cur] != cur+1 && nums[cur] >= 1 && nums[cur] < len) {
                if (nums[cur] != nums[nums[cur] - 1]) {
                    swap(nums, cur, nums[cur] - 1);
                    continue;
                }
            }
            cur++;
        }
        for (int i=0;i<len;i++) {
            if (nums[i] != i+1) {
                return i+1;
            }
        }
        return len+1;
    }

    private void swap(int[] nums, int from, int to) {
        int temp = nums[from];
        nums[from] = nums[to];
        nums[to] = temp;
    }

    //原地hash法
    public int firstMissingPositive2(int[] nums) {
        int len = nums.length;
        for (int i=0;i<len;i++) {
            if (nums[i] <= 0) {
                nums[i] = len+1;
            }
        }
        for (int i=0;i<len;i++) {
            int pos = Math.abs(nums[i]) - 1;
            if (pos < len) {
                nums[pos] = -1 * Math.abs(nums[pos]);
            }
        }
        for (int i=0;i<len;i++) {
            if (nums[i] > 0) {
                return i+1;
            }
        }
        return len+1;
    }
}
